package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//
// Created by ✎﹏ℳ๓独赏☆独醉 on 2024/5/18.
//
//https://leetcode.cn/problems/permutations/description/
public class 全排列 {
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        List<List<Integer>> res = permute(nums);
        System.out.println(res);
    }
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length == 0)return res;
        List<Integer> temp = new ArrayList<>();
        boolean[] flag = new boolean[nums.length];
        dfs(res,temp,flag,nums,0);
        return res;
    }

    private static void dfs(List<List<Integer>> res, List<Integer> temp, boolean[] flag,int[] nums,int step) {
        if(step >= nums.length){
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(!flag[i]){
                temp.add(nums[i]);
                flag[i] = true;
                dfs(res,temp,flag,nums,step + 1);
                flag[i] = false;
                temp.remove(step);
            }
        }
    }
}
